A classifier is a function that classifies inputs by computing a function on a set of inputs. Classifiers are generally computed from a set of learning data and then employed to classify input data. Many practical applications employ classifiers, including pattern recognition, regression estimation, “SPAM” detection, intrusion detection, and so forth. Classifiers can be used to determine, for example, whether an image contains a particular type of object, such as a chair.
A support vector machine (SVM) is a type of classifier. An SVM operates by identifying a hyper-surface in a space of possible inputs by analyzing training data. The hyper-surface attempts to divide “positive” examples in the space of possible inputs from “negative” examples by maximizing the distance (“Euclidian distance”) between the nearest of the positive and negative examples to the hyper-surface. An input is classified as positive or negative depending on which side of the hyper-surface the classifier places the input.
Multiple classifiers can be designed or “learned” to classify data, and these classifiers can be distinguished from one another based on the tradeoff they achieve between discriminative power and invariance. Discriminative power is a measure of a capability to distinguish between types of inputs, e.g., chairs in images. Invariance is a measure of a capability to distinguish between attributes of the inputs, e.g., rotation, zoom, color, and so forth. As examples, image patches, when compared using standard Euclidean distance, have almost no invariance but very high discriminative power because a classifier can compare image patches pixel-by-pixel to determine whether there is a match, but it cannot resolve attributes of the input (e.g., rotation). Alternatively, a constant function has very high invariance but no discriminative power because a classifier employing the function can compute the result of the constant function to classify an input, but different types of objects may not be adequately defined by the constant function.
Classifiers are often generated between these two extremes of discriminative power and invariance, and the concomitant tradeoff affects the generalization performance of classifiers. However, this tradeoff often varies according to the specific classification task at hand. As an example, if all objects in images are known to be chairs of a certain design but in various positions, discriminative power can be traded off to improve invariance. As another example, when classifying digits, a rotationally invariant classifier may not be desirable because then a “6” could be mistaken for a “9.” If the task was simplified to distinguish between just “4” and “9,” then it would be preferable to have full rotational invariance if the digits could occur at any arbitrary orientation. However, “4” and “9” can be confused during image classification. If a rich training corpus of training data is available with digits present at various different orientations, then a more discriminative and less invariant classifier can be employed to classify input data. In this scenario, the data itself would provide the rotation invariance. When multiple classifiers are available to classify data, it can be difficult to decide how to automatically combine the classifiers to provide accurate classification.